package done.normal_601_700;

import com.study.common.TreeNode;
import org.junit.Test;

import java.util.*;

import static com.study.util.LogUtil.info;

/**
 * 655. Print Binary Tree 输出二叉树
 * <p>
 * 在一个 m*n 的二维字符串数组中输出二叉树，并遵守以下规则：
 * 行数 m 应当等于给定二叉树的高度。
 * 列数 n 应当总是奇数。
 * 根节点的值（以字符串格式给出）应当放在可放置的第一行正中间。
 * 根节点所在的行与列会将剩余空间划分为两部分（左下部分和右下
 * 部分）。你应该将左子树输出在左下部分，右子树输出在右下部分。
 * 左下和右下部分应当有相同的大小。即使一个子树为空而另一个非
 * 空，你不需要为空的子树输出任何东西，但仍需要为另一个子树留出
 * 足够的空间。然而，如果两个子树都为空则不需要为它们留出任何空间。
 * 每个未使用的空间应包含一个空的字符串""。
 * 使用相同的规则输出子树。
 * <p>
 * 示例 1:
 * 输入:
 * 1
 * /
 * 2
 * 输出:
 * [[ "", "1", ""],
 * ["2",  "", ""]]
 * 示例 2:
 * 输入:
 * 1
 * / \
 * 2   3
 * \
 * 4
 * 输出:
 * [["",  "",  "", "1", "",  "", ""],
 * ["", "2",  "",  "", "", "3", ""],
 * ["",  "", "4",  "", "",  "", ""]]
 * <p>
 * 2019-04-20 7:46 PM
 **/
@SuppressWarnings("all")
public class PrintBinaryTree {

    public List<List<String>> printTree(TreeNode root) {
        // 190421 first
        return null;
    }

    @Test
    public void test() {
        List list = printTree(new TreeNode(1,
                new TreeNode(2,
                        3, 4), new TreeNode(5,
                6, 7)));
        for (int i = 0; i < list.size(); i++)
            info(list.get(i));
    }
}




































/*
public List<List<String>> printTree(TreeNode root) {
    if (root == null)
        return new ArrayList<>();

    // 初始4
    // 先获得树高再说
    // row 二维数组的【行】
    int row = getLevel(root);

    // 计算列数
    // col 二维数组的【列】
    int col = (int) pow(2.0, row) - 1;

    List<List<String>> ret = new ArrayList<>();

    // 初始化这个二维数组都为""
    for (int i = 0; i < row; i++) {
        List<String> temp = new ArrayList<String>();
        for (int j = 0; j < col; j++)
            temp.add("");

        ret.add(temp);
    }

    dfs(ret, root,0,0, col);
    return ret;

}

// 递归计算每一层 left:最左边  right:最右边
public void dfs(List<List<String>> ret, TreeNode root, int row, int left, int right) {
    if (root != null) {
        // 需要填写字母的位置
        // 当前树根所在坐标
        int mid = (left + right) / 2;

        // 获取第row行第mid列修改其值
        // 打印树根
        ret.get(row).set(mid, "" + root.val);

        // row+1是下一行 root.left为左侧
        // 树根的左边
        dfs(ret, root.left, row + 1,left, mid);

        // row+1是下一行 root.right为右侧
        // 树根的右边
        dfs(ret, root.right, row + 1 , mid + 1, right);
    }
}

// 获得树深度
public int getLevel(TreeNode root) {
    if (root == null)
        return 0;
    return 1 + max(getLevel(root.left), getLevel(root.right));
}
*/